import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-25
 * Time: 23:30
 */
public class Solution {
    public List<Integer> store=new ArrayList<>();
    public List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        dfs(0,nums);
        return ans;
    }

    //index表示固定到了第几位
    public void dfs(int index,int[] nums){
        if(index>=nums.length){
            return;
        }
        if(index==nums.length-1){
            this.store.add(nums[index]);
            //注意注意
            //这里必须是重新new一个数组,因为ans里面存储的都是地址,
            //若直接将store放进去,最后ans里面的地址全部指向store
            //最后得到的ans里面全是空值,因为每次递归完都删除了里面的元素
            //最后已经把store给清空了
            this.ans.add(new ArrayList<>(this.store));
            this.store.remove(this.store.size()-1);
            return ;
        }
        //没有固定到最后一位
        for(int i=index;i<nums.length;i++){
            //将不同的元素放在该位置进行递归
            swap(nums,i,index);
            this.store.add(nums[index]);
            dfs(index+1,nums);
            //再交换过来
            swap(nums,i,index);
            this.store.remove(this.store.size()-1);
        }
    }

    public void swap(int[] arr,int index1,int index2){
        int temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }
}
